package algorithm.disjoint.union;

/**
 * 项目名称: god
 * 包 名 称: algorithm.disjoint.union
 * 类 名 称: UnionFindQuickUnion
 * 类 描 述: TODO
 * 创建时间: 2020/6/30 9:34 上午
 * 创 建 人: Justice
 */
public class UnionFindQuickUnion extends UnionFind {
    public UnionFindQuickUnion(int capacity) {
        super(capacity);
    }

    @Override
    public int find(int v) {
        // 通过parent链条不断地向上找，直到找到根节点
        rangeCheck(v);
        while (v != parents[v]) {
            v = parents[v];
        }
        return v;
    }

    @Override
    public void union(int v1, int v2) {
        // 将v1的根节点嫁接到v2的根节点上
        int p1 = find(v1);
        int p2 = find(v2);
        if (p1 == p2) return;
        parents[p1] = p2;
    }
}
